This section is intended to introduce the reader to various aspects of art, which may be related to various aspects of the present invention that are described and/or claimed below. This discussion is believed to be helpful in providing the reader with background information to facilitate a better understanding of the various aspects of the present invention. Accordingly, it should be understood that these statements are to be read in this light, and not as admissions of prior art.
In 1984, Goldwasser-Micali described a public key encryption scheme; see Shafi Goldwasser and Silvio Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28:270-299, 1984. The scheme has a particular interest because is proved under the Quadratic Residuosity Assumption, but it is not efficient in terms of bandwidth as each bit in the plaintext is expanded to the size of the composite modulus in ciphertext.
A first tentative to improve the efficiency of such scheme is due to Blum-Goldwasser (Manuel Blum and Shafi Goldwasser. An efficient probabilistic public-key encryption scheme which hides all partial information. In CRYPTO, pages 289-302, 1984). Their scheme achieves a better ciphertext expansion: the ciphertext has the same length of the plaintext plus an integer of the size of modulus. The scheme is proved semantically secure under the unpredictability of output of the Blum-Blum-Shub's pseudorandom generator which resides on factorisation hardness assumption. (See Lenore Blum, Manuel Blum, and Mike Shub. Comparison of two pseudo-random number generators. In CRYPTO, pages 61-78, 1982 and Lenore Blum, Manuel Blum, and Mike Shub. A simple unpredictable pseudo-random number generator. SIAM J. Comput., 15(2):364-383, 1986.) Details about the Blum-Goldwasser scheme can be found in The Foundations of Modern Cryptography by Oded Goldreich, 1997.
After the initial work by Golwasser and Micali, Benaloh and Fisher proposed a first generalisation of the Golwasser-Micali encryption scheme based on a Prime Residuosity Assumption. (See Josh Daniel Cohen Benaloh. Verifiable secret-ballot elections. PhD thesis, New Haven, Conn., USA, 1987, and Josh D. Cohen and Michael J. Fischer. A robust and verifiable cryptographically secure election scheme. In SFCS '85: Proceedings of the 26th Annual Symposium on Foundations of Computer Science, pages 372-382, Washington, DC, USA, 1985. IEEE Computer Society.) The basic idea is to consider as message space Z/eZ for a particular small prime e instead of Z/2Z as in Goldwasser-Micali, so achieving a better ciphertext expansion. The main disadvantage of this scheme is that the decryption algorithm is very inefficient requiring a kind of exhaustive search (requiring then a small value of prime e to be practical).
An improved variant of this latter was given by Naccache and Stern considering e not as a prime but a product of small primes. This allows a faster decryption. (See David Naccache and Jacques Stern. A new public key cryptosystem based on higher residues. In ACM Conference on Computer and Communications Security, pages 59-66, 1998.)
A different approach of the same problem was proposed by Okamoto and Uchiyama who suggested to work with a particular modulus N=p2q. This choice improves the bandwidth using as message space Z/pZ. (See Tatsuaki Okamoto and Shigenori Uchiyama. A new public-key cryptosystem as secure as factoring. In EUROCRYPT, pages 308-318, 1998.) Unfortunately, the scheme is vulnerable to a chosen-ciphertext attack that allows to recover the modulus factorisation, completely breaking the system.
Later, Paillier generalised the Okamoto-Uchiyama cryptosystem using N2, the square of a standard composite modulus. The underlying problem used to prove the scheme is the N-th residuosity assumption. (See Pascal Paillier. Public-key cryptosystems based on composite degree residuosity classes. In EUROCRYPT, pages 223-238, 1999.)
Other applications of the more general theory of characters and residuosity can be found also in works by Monnerat and Vaudenay in the domain of undeniable signatures. (See Jean Monnerat, Yvonne Anne Oswald, and Serge Vaudenay. Optimization of the mova undeniable signature scheme. In Dawson and Vaudenay [9], pages 196-209; Jean Monnerat and Serge Vaudenay. Generic homomorphic undeniable signatures. In Pil Joong Lee, editor. Advances in Cryptology—ASIACRYPT 2004, Proceedings, volume 3329 of Lecture Notes in Computer Science. Springer, 2004, pages 354-371; and Jean Monnerat and Serge Vaudenay. Undeniable signatures based on characters: How to sign with one bit. In F. Bao et al., editors, Public Key Cryptography—PKC 2004, volume 2947 of Lecture Notes in Computer Science, pages 69-75. Springer-Verlag, 2004.) In these works, the authors focus on character of order 2, 3 and 4. The authors also provide an analysis and a classification of the problems related to the security of their schemes. Using the general theory of character in building cryptosystem appears also in “Undeniable signatures . . . ” already mentioned and in a work by Renate Scheidler and Hugh C. Williams: A public-key cryptosystem utilizing cyclotomic fields. Des. Codes Cryptography, 6(2):117-131, 1995.
It can therefore be appreciated that there is a need for a solution that improves the Goldwasser-Micali scheme in that it improves the bandwidth while remaining proved secure under standard hardness assumption. This invention provides such a solution.